package com.yww.leetcode.recursion.fibonacci;

import java.util.Arrays;

/**
 * @author yww
 * @description 70. 爬楼梯
 * @since 2024/1/31 14:57
 */
public class ClimbStairs70 {

    // 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
    // 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
    // 缓存优化
    public int climbStairs(int n) {
        int[] cache = new int[n + 2];
        Arrays.fill(cache, -1);
        cache[0] = 1;
        cache[1] = 1; // 一层楼梯只有一种爬法
        cache[2] = 2; // 二层楼梯只有二种爬法
        return climb01(n, cache);
    }

    // 爬第n层楼梯的方法，一次只能跨一步或者是二步
    public static int climb01(int n, int[] cache) {
        if (cache[n] != -1) {
            return cache[n];
        }
        cache[n] = climb01(n - 1, cache) + climb01(n - 2, cache);
        return cache[n];
    }

}
